package mytree.impl;

import mytree.MyBinaryTree;
import mytree.Mytree;

/**
 * Created by Administrator on 2017/4/27.
 */
public class Mytreeimpl<E> implements MyBinaryTree<E>{
    //    建立二叉树（生成根结点和左右子树的二叉树）
/*    @Override
    public void creat(E val, Mytree<E> lChild, Mytree<E> rChild) {

    }*/
    Mytree<E> head=null;
    /*初始化的时候自动创建一个二叉树*/
    public Mytreeimpl() {
    }
    public Mytreeimpl(E val, Mytree<E> lChild, Mytree<E> rChild) {
        //将根结点赋值给头结点
        Mytree<E> p=new Mytree<E>(val,lChild,rChild);
        head=p;
    }
    //    获得左子树(获得树根结点的左子树)
    @Override
    public Mytree<E> getLChild(Mytree<E> p) {
        Mytree<E> temp=p.getlChild();
        return temp;
    }
    //    获得右子树
    @Override
    public Mytree<E> getrChild(Mytree<E> p) {

        return p.getrChild();
    }
    //    插入结点到左子树(新结点插入到左子树)
    @Override
    public void insertL(E val, Mytree<E> p) {
        Mytree<E> temp=new Mytree<E>(val,null,null);
        /*先将根结点的左孩子赋值给新结点的左孩子*/
        temp.setlChild(p.getlChild());
        /*再把新结点的左孩子赋值根结点的左孩子*/
        p.setlChild(temp);
    }
    //    插入结点到右子树
    @Override
    public void insertR(E val, Mytree<E> p) {
        Mytree<E> temp=new Mytree<E>(val,null,null);
        /*先将根结点的右孩子赋值给新结点的右孩子*/
        temp.setrChild(p.getrChild());
        /*再把新结点的右孩子赋值根结点的右孩子*/
        p.setrChild(temp);
    }
    //    删除左子树(删除某个结点的左子树)
    @Override
    public Mytree<E> deleteL(Mytree<E> p) {
        if (p==null||p.getlChild()==null){
            return null;
        }
        Mytree<E> temp=p.getlChild();
        p.setlChild(null);
        return temp;
    }
    //    删除右子树
    @Override
    public Mytree<E> deleteR(Mytree<E> p) {
        if (p==null||p.getrChild()==null){
            return null;
        }
        Mytree<E> temp=p.getrChild();
        p.setrChild(null);
        return temp;
    }
    //    查找结点(查找数据元素与某个结点元素相同的结点)
    //给一个数，从二叉树中查找值为val的结点
    /*root是完整的值，val要查找的值*/
    @Override
    public Mytree<E> search(Mytree<E> root, E val) {
        /*1.先判断root是否为空，如果为null，则返回null*/
        Mytree<E> p=root;
        if (p==null){
            return null;
        }
        /*2.如果根结点的值为val，直接返回val*/
        if (p.getData().equals(val)){
            return p;
        }
        /*3.如果2不成功，找根结点的左孩子*/
        Mytree<E> temp=null;
        if (p.getlChild()!=null){
            temp=search(p.getlChild(),val);
        }
        /*4.找root根结点的右孩子*/
        if (p.getrChild()!=null){
            temp=search(p.getrChild(),val);
        }
        return temp;
    }
    //    遍历二叉树（按某种方式遍历二叉树的全部结点）
    //因为二叉树有很多中遍历方式，i表示用那种遍历方式
    @Override
    public void traverse(Mytree<E> root, int i) {
        if (i==1){
            preorder(root);
        }else if (i==2){
            minorder(root);
        }else if (i==3){
            postorder(root);
        }else {
            System.out.println("请输入正确的遍历方式");
        }
    }

    public void setHead(Mytree<E> head) {
        this.head = head;
    }

    public Mytree<E> getHead() {
        return head;
    }
    public void preorder(Mytree<E> p){
        //先判断是否为空
        if (isEmpty()){
            System.out.println("二叉树为空");
            return;
        }
        //遍历
        if (p !=null){
            //先根
            System.out.print(p.getData());
            //左
            preorder(p.getlChild());
            //右
            preorder(p.getrChild());
        }
    }
    public void minorder(Mytree<E> p){
        //先判断是否为空
        if (isEmpty()){
            System.out.println("二叉树为空");
            return;
        }
        //遍历
        if (p!=null){
            //左
            preorder(p.getlChild());
            //先根
            System.out.print(p.getData());

            //右
            preorder(p.getrChild());
        }
    }
    public void postorder(Mytree<E> p){
        //先判断是否为空
        if (isEmpty()){
            System.out.println("二叉树为空");
            return;
        }
        //遍历
        if (p!=null){
            //左
            preorder(p.getlChild());
            //右
            preorder(p.getrChild());
            //先根
            System.out.print(p.getData());


        }
    }
    public boolean isEmpty(){
        return head==null;
    }
}
